Spacer

Limit pamięci: 256 MB

Las, w którym bajtAlina zbiera maliny składa się z n polan połączonych m jednokierunkowymi ścieżkami. Na niektórych z tych dróg rosną piękne kwiaty, na innych zaś leżą butelki pozostawione przez GraMbca, a jeszce innymi można trafić do Krainy Grzybów. Z tego powodu chodzenie jednymi ścieżkami może być bardziej męczące niż innymi (w niektórych przypadkach może być nawet problem z powrotem).
bajtAlina każdej z dróg przypisała liczbę całkowitą z przedziału [-10⁹; 10⁹], oznaczające poziom jej zmęczenia po przejściu daną ścieżką (liczby ujemne oznaczają, że bajtAlina wypoczywa przechodząc; dodatnia, że okropnie się męczy). Poziom zmęczenia bajtAliny po wycieczce w lesie to średnia liczb nadanych drogom na trasie spaceru.

bajtAlina chciałaby przejść się po lesie w poszukiwaniu malin. Ustaliła, że jej trasa powinna zaczynać się i kończyć na tej samej polance. Jaką najmniej męczącą trasę może wybrać?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n, m (2 <= n <= 100, 1 <= m <= 10 000) oznaczających liczbę polan i liczbę dróg w lesie. W kolejnych m wierszach znajdują się opisy kolejnych dróg. Opis drogi składa się z trzech liczb a_i, b_i i c_i, oznaczających, że i-ta droga prowadzi z polany a_i do polany b_i o poziomie zmęczenia c_i. Drogi nie przecinają się ze sobą, jednak mogą prowadzić mostami i tunelami.

Wyjście

Na wyjście wypisz pojedynczą liczbę oznaczającą minimalny poziom zmęczenia, jaki może osiągnąć bajtAlina spacerując po lesie. Wynik zostanie uznany za poprawny, jeśli będzie różnił się od optymalnego o co najwyżej 0.01.

Przykład

Dla danych:

4 5
2 3 3
1 4 -2
4 3 10
3 1 2
1 2 2

Poprawnym wynikiem jest:

2.33

Pobierz plik wejściowy